/*-------------------------------------------------------------------------
 *
 * tsquery_util.c
 *	  tsquery 数据类型的实用程序
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 *
 *
 * IDENTIFICATION
 *	  src/backend/utils/adt/tsquery_util.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "miscadmin.h"
#include "tsearch/ts_utils.h"

/*
 * 为以QueryItem数组格式给定的tsquery构建QTNode树。
 */
QTNode * QT2QTN(QueryItem *fc_in, char *fc_operand)
{
	QTNode	   *fc_node = (QTNode *) palloc0(sizeof(QTNode));

	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	fc_node->valnode = fc_in;

	if (fc_in->type == QI_OPR)
	{
		fc_node->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);
		fc_node->child[0] = QT2QTN(fc_in + 1, fc_operand);
		fc_node->sign = fc_node->child[0]->sign;
		if (fc_in->qoperator.oper == OP_NOT)
			fc_node->nchild = 1;
		else
		{
			fc_node->nchild = 2;
			fc_node->child[1] = QT2QTN(fc_in + fc_in->qoperator.left, fc_operand);
			fc_node->sign |= fc_node->child[1]->sign;
		}
	}
	else if (fc_operand)
	{
		fc_node->word = fc_operand + fc_in->qoperand.distance;
		fc_node->sign = ((uint32) 1) << (((unsigned int) fc_in->qoperand.valcrc) % 32);
	}

	return fc_node;
}

/*
 * 释放QTNode树。
 *
 * 如果通过标记标记为瞬态，则释放引用的“word”和“valnode”项。
 */
void QTNFree(QTNode *fc_in)
{
	if (!fc_in)
		return;

	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_in->valnode->type == QI_VAL && fc_in->word && (fc_in->flags & QTN_WORDFREE) != 0)
		pfree(fc_in->word);

	if (fc_in->valnode->type == QI_OPR)
	{
		int			fc_i;

		for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
			QTNFree(fc_in->child[fc_i]);
	}
	if (fc_in->child)
		pfree(fc_in->child);

	if (fc_in->flags & QTN_NEEDFREE)
		pfree(fc_in->valnode);

	pfree(fc_in);
}

/*
 * QTNodes的排序比较器。
 *
 * 排序顺序是相对任意的。
 */
int QTNodeCompare(QTNode *fc_an, QTNode *fc_bn)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_an->valnode->type != fc_bn->valnode->type)
		return (fc_an->valnode->type > fc_bn->valnode->type) ? -1 : 1;

	if (fc_an->valnode->type == QI_OPR)
	{
		QueryOperator *fc_ao = &fc_an->valnode->qoperator;
		QueryOperator *fc_bo = &fc_bn->valnode->qoperator;

		if (fc_ao->oper != fc_bo->oper)
			return (fc_ao->oper > fc_bo->oper) ? -1 : 1;

		if (fc_an->nchild != fc_bn->nchild)
			return (fc_an->nchild > fc_bn->nchild) ? -1 : 1;

		{
			int			fc_i,
						fc_res;

			for (fc_i = 0; fc_i < fc_an->nchild; fc_i++)
				if ((fc_res = QTNodeCompare(fc_an->child[fc_i], fc_bn->child[fc_i])) != 0)
					return fc_res;
		}

		if (fc_ao->oper == OP_PHRASE && fc_ao->distance != fc_bo->distance)
			return (fc_ao->distance > fc_bo->distance) ? -1 : 1;

		return 0;
	}
	else if (fc_an->valnode->type == QI_VAL)
	{
		QueryOperand *fc_ao = &fc_an->valnode->qoperand;
		QueryOperand *fc_bo = &fc_bn->valnode->qoperand;

		if (fc_ao->valcrc != fc_bo->valcrc)
		{
			return (fc_ao->valcrc > fc_bo->valcrc) ? -1 : 1;
		}

		return tsCompareString(fc_an->word, fc_ao->length, fc_bn->word, fc_bo->length, false);
	}
	else
	{
		elog(ERROR, "unrecognized QueryItem type: %d", fc_an->valnode->type);
		return 0;				/* 保持编译器安静 */
	}
}

/*
 * QTNode指针的qsort比较器。
 */
static int fc_cmpQTN(const void *fc_a, const void *fc_b)
{
	return QTNodeCompare(*(QTNode *const *) fc_a, *(QTNode *const *) fc_b);
}

/*
 * 通过将AND/OR节点的子节点排序为一种任意但定义良好的顺序，
 * 使QTNode树规范化。
 */
void QTNSort(QTNode *fc_in)
{
	int			fc_i;

	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_in->valnode->type != QI_OPR)
		return;

	for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
		QTNSort(fc_in->child[fc_i]);
	if (fc_in->nchild > 1 && fc_in->valnode->qoperator.oper != OP_PHRASE)
		qsort((void *) fc_in->child, fc_in->nchild, sizeof(QTNode *), fc_cmpQTN);
}

/*
 * 根据QTNodeCompare判断两个QTNode树是否相等？
 */
bool QTNEq(QTNode *fc_a, QTNode *fc_b)
{
	uint32		fc_sign = fc_a->sign & fc_b->sign;

	if (!(fc_sign == fc_a->sign && fc_sign == fc_b->sign))
		return false;

	return (QTNodeCompare(fc_a, fc_b) == 0);
}

/* 
 * 删除不必要的中间节点。例如：
 *
 *	OR			OR
 * a  OR	-> a b c
 *	 b	c
 */
void QTNTernary(QTNode *fc_in)
{
	int			fc_i;

	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_in->valnode->type != QI_OPR)
		return;

	for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
		QTNTernary(fc_in->child[fc_i]);

	/*仅有 AND 和 OR 是结合性的，所以不要扁平化其他节点类型 */
	if (fc_in->valnode->qoperator.oper != OP_AND &&
		fc_in->valnode->qoperator.oper != OP_OR)
		return;

	for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
	{
		QTNode	   *fc_cc = fc_in->child[fc_i];

		if (fc_cc->valnode->type == QI_OPR &&
			fc_in->valnode->qoperator.oper == fc_cc->valnode->qoperator.oper)
		{
			int			fc_oldnchild = fc_in->nchild;

			fc_in->nchild += fc_cc->nchild - 1;
			fc_in->child = (QTNode **) repalloc(fc_in->child, fc_in->nchild * sizeof(QTNode *));

			if (fc_i + 1 != fc_oldnchild)
				memmove(fc_in->child + fc_i + fc_cc->nchild, fc_in->child + fc_i + 1,
						(fc_oldnchild - fc_i - 1) * sizeof(QTNode *));

			memcpy(fc_in->child + fc_i, fc_cc->child, fc_cc->nchild * sizeof(QTNode *));
			fc_i += fc_cc->nchild - 1;

			if (fc_cc->flags & QTN_NEEDFREE)
				pfree(fc_cc->valnode);
			pfree(fc_cc);
		}
	}
}

/*
 * 通过插入中间节点将树转换为二叉树。
 * （QTNTernary 的相反）
 */
void QTNBinary(QTNode *fc_in)
{
	int			fc_i;

	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_in->valnode->type != QI_OPR)
		return;

	for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
		QTNBinary(fc_in->child[fc_i]);

	while (fc_in->nchild > 2)
	{
		QTNode	   *fc_nn = (QTNode *) palloc0(sizeof(QTNode));

		fc_nn->valnode = (QueryItem *) palloc0(sizeof(QueryItem));
		fc_nn->child = (QTNode **) palloc0(sizeof(QTNode *) * 2);

		fc_nn->nchild = 2;
		fc_nn->flags = QTN_NEEDFREE;

		fc_nn->child[0] = fc_in->child[0];
		fc_nn->child[1] = fc_in->child[1];
		fc_nn->sign = fc_nn->child[0]->sign | fc_nn->child[1]->sign;

		fc_nn->valnode->type = fc_in->valnode->type;
		fc_nn->valnode->qoperator.oper = fc_in->valnode->qoperator.oper;

		fc_in->child[0] = fc_nn;
		fc_in->child[1] = fc_in->child[fc_in->nchild - 1];
		fc_in->nchild--;
	}
}

/*
 * 计算树中操作数字符串的总长度（包括 '\0'-终止符）和节点的总数。
 * 调用者必须将 *sumlen 和 *nnode 初始化为零。
 */
static void fc_cntsize(QTNode *fc_in, int *fc_sumlen, int *fc_nnode)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	*fc_nnode += 1;
	if (fc_in->valnode->type == QI_OPR)
	{
		int			fc_i;

		for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
			fc_cntsize(fc_in->child[fc_i], fc_sumlen, fc_nnode);
	}
	else
	{
		*fc_sumlen += fc_in->valnode->qoperand.length + 1;
	}
}

typedef struct
{
	QueryItem  *curitem;
	char	   *operand;
	char	   *curoperand;
} QTN2QTState;

/*
 * 递归地将 QTNode 树转换为扁平的 tsquery 格式。
 * 调用者必须分配正确大小的数组。
 */
static void fc_fillQT(QTN2QTState *fc_state, QTNode *fc_in)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	if (fc_in->valnode->type == QI_VAL)
	{
		memcpy(fc_state->curitem, fc_in->valnode, sizeof(QueryOperand));

		memcpy(fc_state->curoperand, fc_in->word, fc_in->valnode->qoperand.length);
		fc_state->curitem->qoperand.distance = fc_state->curoperand - fc_state->operand;
		fc_state->curoperand[fc_in->valnode->qoperand.length] = '\0';
		fc_state->curoperand += fc_in->valnode->qoperand.length + 1;
		fc_state->curitem++;
	}
	else
	{
		QueryItem  *fc_curitem = fc_state->curitem;

		Assert(fc_in->valnode->type == QI_OPR);

		memcpy(fc_state->curitem, fc_in->valnode, sizeof(QueryOperator));

		Assert(fc_in->nchild <= 2);
		fc_state->curitem++;

		fc_fillQT(fc_state, fc_in->child[0]);

		if (fc_in->nchild == 2)
		{
			fc_curitem->qoperator.left = fc_state->curitem - fc_curitem;
			fc_fillQT(fc_state, fc_in->child[1]);
		}
	}
}

/*
 * 从 QTNode 树构建扁平的 tsquery。
 */
TSQuery QTN2QT(QTNode *fc_in)
{
	TSQuery		fc_out;
	int			fc_len;
	int			fc_sumlen = 0,
				fc_nnode = 0;
	QTN2QTState fc_state;

	fc_cntsize(fc_in, &fc_sumlen, &fc_nnode);

	if (TSQUERY_TOO_BIG(fc_nnode, fc_sumlen))
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("tsquery is too large")));
	fc_len = COMPUTESIZE(fc_nnode, fc_sumlen);

	fc_out = (TSQuery) palloc0(fc_len);
	SET_VARSIZE(fc_out, fc_len);
	fc_out->size = fc_nnode;

	fc_state.curitem = GETQUERY(fc_out);
	fc_state.operand = fc_state.curoperand = GETOPERAND(fc_out);

	fc_fillQT(&fc_state, fc_in);
	return fc_out;
}

/*
 * 复制 QTNode 树。
 *
 * 也会创建可修改的单词和 valnodes 副本。
 */
QTNode * QTNCopy(QTNode *fc_in)
{
	QTNode	   *fc_out;

	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	fc_out = (QTNode *) palloc(sizeof(QTNode));

	*fc_out = *fc_in;
	fc_out->valnode = (QueryItem *) palloc(sizeof(QueryItem));
	*(fc_out->valnode) = *(fc_in->valnode);
	fc_out->flags |= QTN_NEEDFREE;

	if (fc_in->valnode->type == QI_VAL)
	{
		fc_out->word = palloc(fc_in->valnode->qoperand.length + 1);
		memcpy(fc_out->word, fc_in->word, fc_in->valnode->qoperand.length);
		fc_out->word[fc_in->valnode->qoperand.length] = '\0';
		fc_out->flags |= QTN_WORDFREE;
	}
	else
	{
		int			fc_i;

		fc_out->child = (QTNode **) palloc(sizeof(QTNode *) * fc_in->nchild);

		for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
			fc_out->child[fc_i] = QTNCopy(fc_in->child[fc_i]);
	}

	return fc_out;
}

/*
 * 清除 QTNode 树中所有节点的指定标志位。
 */
void QTNClearFlags(QTNode *fc_in, uint32 fc_flags)
{
	/* 由于这个函数递归，它可能导致栈溢出。 */
	check_stack_depth();

	fc_in->flags &= ~fc_flags;

	if (fc_in->valnode->type != QI_VAL)
	{
		int			fc_i;

		for (fc_i = 0; fc_i < fc_in->nchild; fc_i++)
			QTNClearFlags(fc_in->child[fc_i], fc_flags);
	}
}
